// 输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。
// 假设压入栈的所有数字均不相等。例如序列 1,2,3,4,5 是某栈的压入顺序，序列 4,5,3,2,1 是该压栈序列对应的一个弹出序列，
// 但 4,3,5,1,2 就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）
// 解题思路：

// 需要一个辅助栈，来模拟出入栈的过程。算法流程如下：

// - 取压入队列的首元素，将其压入辅助栈
// - 检查辅助栈顶元素是否和弹出队列的首元素相等：
// - 若相等，则辅助栈弹出栈顶元素，弹出队列取出队首元素，重复检查
// - 若不相等，回到第一步
// - 最后，检查辅助栈和弹出队列是否均为空。

// 时间复杂度是 O(N^2)，空间复杂度是 O(N)。

function IsPopOrder(pushV, popV) {
  // write code here
  // 辅助栈temp
  let temp = [];
  pushV.map((item) => {
    if (item === popV[0]) {
      popV.shift();
      while (temp.length && temp[temp.length - 1] === popV[0]) {
        temp.pop();
        popV.shift();
      }
    } else {
      temp.push(item);
    }
  });

  // 当temp临时栈和出栈顺序都为空的时候 说明顺序OK 反之顺序不OK
  if (temp.length > 0 && popV.length > 0) {
    return false;
  } else {
    return true;
  }
}

let arr1 = [1, 2, 3, 4, 5];
let arr2 = [4, 5, 3, 2, 1];
console.log(IsPopOrder(arr1, arr2));
